class Solution {
public:
    /*
    加入数组中存在众数，那么众数一定大于数组的长度的一半。
    思想就是：如果两个数不相等，就消去这两个数，最坏情况下，每次消去一个众数和一个非众数，
    那么如果存在众数，最后留下的数肯定是众数。
    */
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        if(numbers.empty()) return 0;
        size_t size = numbers.size();
        int res = numbers[0];
        int times = 0;
        for(size_t i = 1; i < size; ++i){
            if(0 == times){
                times = 1;
                res = numbers[i];
            }
            else{ 
                if(numbers[i] == res) ++times;
                else  --times;
            }
        }
        
        size_t res_cnt = 0;
        for(size_t i = 0; i < size; ++i){
            if(numbers[i] == res) ++res_cnt;
        }
        return (res_cnt > size/2) ? res : 0;
    }
};